package com.lun.hard;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class RecoverATreeFromPreorderTraversal {

	// 方法一：我写的
	public TreeNode recoverFromPreorder(String traversal) {
		LinkedList<Object[]> stack = new LinkedList<>();
		TreeNode root = null;
		int dashNum = 0;
		for (int i = 0; i < traversal.length(); i++) {
			char curr = traversal.charAt(i);

			if (curr == '-') {
				dashNum++;
			} else {// 读取数
				int value = curr - '0';

				// 预读
				while (i + 1 != traversal.length() && //
						traversal.charAt(i + 1) != '-') {
					value = value * 10 + (traversal.charAt(++i) - '0');
				}

				TreeNode newNode = new TreeNode(value);
				if (root == null) {
					root = newNode;
				} else {
					Object[] topNodeWithDash = stack.peek();
					int topDashNum = (int) topNodeWithDash[0];
					TreeNode topNode = (TreeNode) (topNodeWithDash[1]);

					while (topDashNum >= dashNum) {
						stack.pop();
						topNodeWithDash = stack.peek();
						topDashNum = (int) topNodeWithDash[0];
						topNode = (TreeNode) (topNodeWithDash[1]);
					}

					// topDashNum < dashNum
					if (topNode.left == null)
						topNode.left = newNode;
					else
						topNode.right = newNode;
				}
				stack.push(new Object[] { dashNum, newNode });

				dashNum = 0;
			}
		}

		return root;
	}

	// 方法二：别人写的
	public TreeNode recoverFromPreorder2(String S) {
		String[] tokens = S.split("-");
		List<TreeNode> list = new ArrayList<>();

		list.add(new TreeNode(Integer.valueOf(tokens[0])));
		int level = 1;
		for (int i = 1; i < tokens.length; i++) {

			if (!tokens[i].isEmpty()) {
				TreeNode node = new TreeNode(Integer.valueOf(tokens[i]));
				list.add(level, node);

				TreeNode parent = list.get(level - 1);
				if (parent.left == null) {
					parent.left = node;
				} else {
					parent.right = node;
				}

				level = 1;
			} else {
				level++;
			}
		}

		return list.get(0);
	}

	// 方法三：别人写的，DFS 前序遍历模式 递归法
	public TreeNode recoverFromPreorder3(String S) {
		return helper(S, 0, new int[] { 0 });
	}

	private TreeNode helper(String s, int depth, int[] index) {
		int numDash = 0;
		while (index[0] + numDash < s.length() && s.charAt(index[0] + numDash) == '-') {
			numDash++;
		}
		if (numDash != depth)
			return null;
		
		int next = index[0] + numDash;
		while (next < s.length() && s.charAt(next) != '-')
			next++;
		int val = Integer.parseInt(s.substring(index[0] + numDash, next));
		index[0] = next;
		
		TreeNode root = new TreeNode(val);
		root.left = helper(s, depth + 1, index);
		root.right = helper(s, depth + 1, index);
		return root;
	}
}
